/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-26
 * Time: 22:29
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private int ans;
    public int longestZigZag(TreeNode root) {
        postOrder(root);
        return ans;
    }


    /**
     *  后序遍历
     *  后序遍历的好处是 从下往上只有一条路径
     * @param root
     * @return
     */
    private int[] postOrder(TreeNode root) {
        // 如果为空, 返回 -1, 因为回溯之后都会 + 1 这样才能使只有一个节点的路径长度为 0
        if (root == null) {
            return new int[]{-1, -1};
        }

        // 一个只取左边, 一个只取右边, 就类似与 DP
        // 使得能够取出其中一段

        // 计算左边最长交错路径, 不要忘了 + 1
        int l = postOrder(root.left)[0] + 1;
        // 计算右边最长交错路径, 不要忘了 + 1
        int r = postOrder(root.right)[1] + 1;
        // 更新一下 ans
        int max = Math.max(l, r);
        ans = Math.max(max, ans);
        // 以 0 为左, 1 为 右
        // 因为要求的是交错路径, 所以返回的 顺序是 r l
        return new int[]{r, l};
    }
}
